package com.agile.leetcode.hot.middle;


import java.util.*;

/**
 * 347. 前 K 个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 * @Author:ChenZhangKun
 * @Date: 2021/6/5 21:32
 */
public class TopKFrequent {
    public static void main(String[] args) {
        TopKFrequent topKFrequent = new TopKFrequent();
        int[] nums = {1, 1, 1, 2, 2, 3};
        int[] ints = topKFrequent.topKFrequent(nums, 2);
        System.out.println(Arrays.toString(ints));
    }

    public int[] topKFrequent(int[] nums, int k) {
        // 前k高的数组
        int[] result = new int[k];
        // 统计数据
        Map<Integer, Integer> map = new HashMap<>(16);
        // 遍历
        for (int i = 0; i < nums.length; i++) {
            // 统计个数
            map.compute(nums[i], (key,value)->value==null?1:value+1);
        }
        // 创建优先队列
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        // 遍历map
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 拿到key
            Integer key = entry.getKey();
            // 拿到value
            Integer value = entry.getValue();
            // 判断
            if (priorityQueue.size() == k) {
                // 拿到第一个
                int[] peek = priorityQueue.peek();
                assert peek != null;
                if (value > peek[1]) {
                    // 弹出
                    priorityQueue.poll();
                    priorityQueue.offer(new int[]{key, value});
                }
            } else {
                priorityQueue.offer(new int[]{key, value});
            }
        }
        for (int i = 0; i < k; i++) {
            if (priorityQueue.size() > 0) {
                // 弹出
                int[] poll = priorityQueue.poll();
                result[i] = poll[0];
            }
        }
        return result;

    }
}
